/**
 * 堆排序
 */
Array.prototype.heap = function(){
    let _this = this;
    
    heap();
    function heap(){
         let endkey = Math.floor((_this.length - 2)/2);
         for(let i = endkey ; i>=0; i--){
              heapfity(i,_this.length-1);
         }
         let i = _this.length -1;
         while(i>0){
              swap(0,i);
              i-=1;
              heapfity(0,i);  
         }
    }

    // 元素下沉
    function heapfity(headIndex,endIndex){
        
        let leftSonIndex = headIndex * 2 + 1;
        let rightSonIndex = headIndex * 2 + 2;
        
        if( leftSonIndex > endIndex ) return;
        // 找出左右子节点交大元素的索引
        let bigSonIndex;
        if( rightSonIndex <= endIndex ){
            bigSonIndex = _this[leftSonIndex] >= _this[rightSonIndex] ? leftSonIndex : rightSonIndex;
        }else{
            bigSonIndex = leftSonIndex;
        }

        // 递归构建大顶推
        if(_this[headIndex] < _this[bigSonIndex]){
             swap(headIndex ,bigSonIndex);  
             heapfity(bigSonIndex,endIndex);
        }    
    }

    // 交换数组两个元素的值
    function swap(i,j){
       let temp = _this[i];
       _this[i] = _this[j];
       _this[j] = temp;
    }

}


let a = [1,20,30,1000,-15,100,10,5];
a.heap();
console.log(a);